# -*- coding: utf-8 -*-
# @Time    : 2021/1/4 上午9:39
# @Author  : tgy

class Solution:
    def fib(self, n: int) -> int:
        ...
        container = {0: 0, 1: 1}
        return self.fibPrivate(container, n)

    def fibPrivate(self, container, n):
        ...

        if n in container:
            return container[n]

        result = self.fibPrivate(container, n - 1) + self.fibPrivate(container, n - 2)
        container[n] = result
        return result


if __name__ == '__main__':
    ...
    solution = Solution()
    fib = solution.fib(30)
    print(fib)
